/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.junit.Test;


/**
 * @version 1.0
 * @description Given a binary tree, return the inorder traversal of its
 *              nodes' values.
 * 
 *              Note: Recursive solution is trivial, could you do it
 *              iteratively? 
 */
public class BinaryTreeInorderTraversal {

	private class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null)
			return res;
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		TreeNode cur = null;
		boolean flag = false;
		while (!stack.isEmpty()) {
			cur = stack.peek();
			// if the ahead op is push, continue push left element
			// if the ahead op is pop, means ahead element is cur.left, should not push it again
			if (cur.left != null && !flag) {	
				stack.push(cur.left);
				flag = false;					// false means push op
			} else {
				res.add(cur.val);
				stack.pop();
				flag = true;					// true means pop op
				if (cur.right != null) {
					stack.push(cur.right);
					flag = false;
				}
			}
		}
		
		return res;
	}
	
	@Test
	public void test() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		TreeNode n7 = new TreeNode(7);
		TreeNode n8 = new TreeNode(8);
		TreeNode n9 = new TreeNode(9);
		TreeNode n10 = new TreeNode(10);
		TreeNode n11 = new TreeNode(11);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right  = n7;
		n7.right = n8;
		n4.left = n5;
		n4.right = n6;
		n6.left = n10;
		n6.right = n11;
		n7.left = n9;
		
		List<Integer> res = inorderTraversal(n1);
		for (int i : res) {
			System.out.println(i);
		}
	}
}
